package org.laizili.solution.leetcode;

/**
 * <a href="https://leetcode.cn/problems/kth-smallest-number-in-multiplication-table/">668. 乘法表中第k小的数</a>
 * <p>
 * tags: 二分+计数判定;
 */
public class Problem668 {
    private static class Solution {
        // 二分 + 计数判定
        public int findKthNumber(int m, int n, int k) {
            int left = 1, right = m * n;
            while (left < right) {
                int x = left + (right - left) / 2;
                int count = x / n * n;
                for (int i = x / n + 1; i <= m; ++i) {
                    count += x / i;
                }
                if (count >= k) {
                    right = x;
                } else {
                    left = x + 1;
                }
            }
            return left;
        }
    }

}